package org.ramalho;

/**
 *
 * @author Luciano G. S. Ramalho - n.USP 1002101
 */

import java.util.NoSuchElementException;

public class Vetor<T> {
    private int tam;
    private Celula<T> sentinela;

    public Vetor() {
        tam = 0;
        sentinela = new Celula<T>();
    }

    public Vetor(int tamanho_inicial) {
        Celula<T> atual;
        sentinela = new Celula<T>();
        atual = sentinela;
        for (int i = 0; i < tamanho_inicial; i++) {
            atual.próxima = new Celula<T>(null);
            atual = atual.próxima;
        }
        tam = tamanho_inicial;
    }

    public Vetor(Vetor<T> V) {
        Celula<T> atual;
        sentinela = new Celula<T>();
        atual = sentinela;
        for (int i = 0; i < V.Tamanho(); i++) {
            atual.próxima = new Celula<T>(V.get(i));
            atual = atual.próxima;
        }
        tam = V.Tamanho();
    }

    int Tamanho() {
        return tam;
    }

    public void Insere(T t) {
        inserirCelula(new Celula<T>(t), tam);
        tam++;
    }

    public void Insere(T t, int index) {
        if ((index < 0) || (index >= tam))
            throw new IndexOutOfBoundsException(
                    "nao existe elemento com indice "+index);
        inserirCelula(new Celula<T>(t), index);
        tam++;
    }

    T get(int index) {
        if ((index < 0) || (index >= tam))
            throw new IndexOutOfBoundsException(
                    "nao existe elemento com indice "+index);
        return getCelula(index).carga;
    }

    void set(int index, T t) {
        if (index < 0) // não é permitido setar valor da sentinela
            throw new IndexOutOfBoundsException(
                    "nao existe elemento com indice "+index);
        Celula<T> cel = getCelula(index);
        cel.carga = t;
    }

    public void Remove(int index) {
        Celula<T> anterior = getCelula(index-1);
        if (anterior.próxima == null)
            throw new IndexOutOfBoundsException(
                    "nao existe elemento com indice "+index);
        anterior.próxima = anterior.próxima.próxima;
        tam--;
    }

    public void Remove(T t) {
        Celula<T> anterior = buscarCelulaAnterior(t);
        if (anterior == null)
            throw new NoSuchElementException("não existe elemento com valor "+t);
        anterior.próxima = anterior.próxima.próxima;
        tam--;
    }

    void RemoveTodos(T t) {
        boolean removeu = false;
        while (true) {
            try {
                Remove(t);
                removeu = true;
            } catch (NoSuchElementException e) {
                break;
            }
        }
        if (! removeu)
            throw new NoSuchElementException("não existe elemento com valor "+t);
    }

    int BuscaBinaria(T t) {
        if (! ordenado())
            throw new UnsupportedOperationException(
                    "Obrigatório ordenar o Vetor antes de invocar BuscaBinaria");
        int i;
        int cmp;
        int abaixo = -1;
        int acima = tam;
        while (abaixo < (acima - 1)) {
            i = (acima + abaixo) / 2;
            cmp = ((Comparable<T>)t).compareTo(get(i));
            if (cmp == 0)
                return i;
            else {
                if (cmp < 0)
                    acima = i;
                else
                    abaixo = i;
            }
        }
        return -1;
    }

    void Ordena() {
        T val_min;
        Celula<T> anterior;
        for (int i = 0; i < (tam-1); i++) {
            val_min = valorMínimo(i);
            anterior = buscarCelulaAnterior(val_min);
            if (anterior.próxima != getCelula(i)) {
                anterior.próxima = anterior.próxima.próxima;
                inserirCelula(new Celula(val_min), i);
            }
        }
    }
    
    /* métodos auxiliares */

    Celula<T> getSentinela() { // util para testar
        return sentinela;
    }

    Celula<T> getCelula(int index) { // Celula -1 é a sentinela
        Celula<T> atual = sentinela;
        if ((index < -1) || (index >= tam))
            throw new IndexOutOfBoundsException(
                    "nao existe elemento com indice "+index);
        for (int i = -1; i < index; i++)
            atual = atual.próxima;
        return atual;
    }

    Celula<T> buscarCelula(T t) {
        Celula<T> atual = sentinela.próxima;
        while (atual != null) {
            if ((atual.carga == t) ||
                    ((atual.carga != null) && atual.carga.equals(t)))
                return atual;
            atual = atual.próxima;
        }
        return atual;
    }

    Celula<T> buscarCelulaAnterior(T t) {
        Celula<T> anterior = sentinela;
        Celula<T> atual = sentinela.próxima;
        while (atual != null) {
            if ((atual.carga == t) ||
                    ((atual.carga != null) && atual.carga.equals(t)))
                return anterior;
            anterior = atual;
            atual = atual.próxima;
        }
        return null;
    }

    boolean ordenado() {
        Celula<T> atual = sentinela.próxima;
        while ((atual != null) && (atual.próxima != null)) {
            if (atual.compareTo(atual.próxima) > 0)
                return false;
            atual = atual.próxima;
        }
        return true;
    }

    T valorMínimo(int index) { // mínimo a partir de uma posicao //
        T min;
        Celula<T> atual = getCelula(index);
        min = atual.carga;
        while (atual.próxima != null) {
            if (((Comparable<T>)min).compareTo(atual.próxima.carga) > 0)
                min = atual.próxima.carga;
            atual = atual.próxima;
        }
        return min;
    }

    void inserirCelula(Celula<T> nova, int index) {
        Celula<T> anterior = getCelula(index-1);
        nova.próxima = anterior.próxima;
        anterior.próxima = nova;
    }

}
